/*!
 * \file HeuristicasGolosas.cpp
 *
 * \date May 9, 2014
 * \author correa
 */
#include "HeuristicasGolosas.h"
#include <Lista.h>

using namespace std;

HeuristicasGolosas::HeuristicasGolosas(Grafo &grafo) : _grafo(grafo), _orden(_grafo.vertices().lista()),
		_ll(*(new Lista(_grafo.getN()))),
		_RR(new VertexSet(_grafo.getN())), _SS(new VertexSet(_grafo.getN())),
		_candidatos(new VertexSet(_grafo.getN())), _stableset(new VertexSet(_grafo.getN())),
		_mejor(0)
{
}

HeuristicasGolosas::~HeuristicasGolosas()
{
	delete &_ll;
	delete _RR;
	delete _SS;
	delete _candidatos;
	delete _stableset;
	delete &_orden;
}

int HeuristicasGolosas::rounding(DoubleValueArray& pesos, Lista &intera) {
	struct ComparadorPesosGradosDecrecientes {
		Grafo const * _g;
		DoubleValueArray const * _pesos;
		bool operator() (int a, int b) { return (*_pesos)[a] > (*_pesos)[b] ? true : (*_pesos)[a] == (*_pesos)[b] ? _g->vecinos(a).size() < _g->vecinos(b).size() : false; }
	} _compPesosGradosDecrecientes;
	_compPesosGradosDecrecientes._g = &_grafo;
	_compPesosGradosDecrecientes._pesos = &pesos;
	sort(_orden.begin(), _orden.end(), _compPesosGradosDecrecientes);

	_RR->addAll();

	int i,v;
	for (i = 0; i < _orden.cantidad(); i++) {
		v = _orden[i];
		if (_RR->contains(v))
		{
			intera += v;
			_RR->removeAll(_grafo.vecinos(v));
			_RR->remove(v);
		}
	}

	if (intera.cantidad() > _mejor)
		_mejor = intera.cantidad();
//	if (intera.cantidad() < 0.75*_mejor)
//		return intera.cantidad();

	int cursz = 0;

	bool improved = false;
	_candidatos->addAll();
	while (!_candidatos->isEmpty())
	{
		int l = _candidatos->least();
		_stableset->removeAll();
		_RR->addAll();

		_stableset->add(l);
		cursz = 1;
		_RR->removeAll(_grafo.vecinos(l));
		_RR->remove(l);

		_candidatos->remove(l);

		int i,v;
		for (i = 0; i < _orden.cantidad(); i++) {
			v = _orden[i];
			if (_RR->contains(v))
			{
				_stableset->add(v);
				cursz++;
				_RR->removeAll(_grafo.vecinos(v));
				_RR->remove(v);

				_candidatos->remove(v);
			}
		}

		if (cursz > intera.cantidad())
		{
			intera.clear();
			_stableset->lista(intera);
			improved = true;
		}
	}

	if (intera.cantidad() > _mejor)
		_mejor = intera.cantidad();
//	if (intera.cantidad() < 0.80*_mejor)
//		return intera.cantidad();

	if (true) //!improved)
	{
		int j;
		for (j = intera.cantidad()-5; j >= 0 && pesos[intera[j]] < 1.0-1.0e-5; j--)
		{
			_RR->addAll();

			int k;
			for (k = 0; k < intera.cantidad(); k++)
				if (k != j)
				{
					_RR->removeAll(_grafo.vecinos(intera[k]));
					_RR->remove(intera[k]);
				}

			_RR->retainAll(_grafo.vecinos(intera[j]));
			_ll.clear();
			_RR->lista(_ll);

			for (i = 0; i < _ll.cantidad(); i++) {
				_RR->remove(_ll[i]);
				_SS->copyAll(*_RR);
				_SS->removeAll(_grafo.vecinos(_ll[i]));

				v = _SS->least();
				if (v >= 0)
				{
					intera.remove(j);
					intera += _ll[i];
					intera += v;

					_SS->remove(v);
					_SS->removeAll(_grafo.vecinos(v));

					v = _SS->least();
					while (v >= 0)
					{
						intera += v;

						_SS->remove(v);
						_SS->removeAll(_grafo.vecinos(v));

						v = _SS->least();
					}

					i = _ll.cantidad();
					//				j = intera.cantidad()-3;
				}
			}
		}
	}

	if (intera.cantidad() > _mejor)
		_mejor = intera.cantidad();

	return intera.cantidad();
}
